package q1981_minimizeTheDifference;

import java.util.Arrays;

public class Solution_1 {
    private Integer min = Integer.MAX_VALUE;
    private int m = 0;
    private int n = 0;
    private boolean[][] memo = new boolean[71][5000];
    /*
    最小化目标值与所选元素的差
    DFS + 剪枝 + 记忆化搜索的方式
    首先对每一行都进排序 当当前值已经大于目标值并且两者之差已经超过最小值了，就不需要进行当前层后续的遍历了，直接break
     */
    public int minimizeTheDifference(int[][] mat, int target) {
        m = mat.length;
        n = mat[0].length;
        for (int[] arr : mat) {
            Arrays.sort(arr);
        }
        backtrackingMinimize(mat, target, 0, 0);
        return min;
    }

    private void backtrackingMinimize(int[][] mat, int target, int startIndex, int cnt) {
        if (startIndex == m) {
            min = Math.min(min, Math.abs(target - cnt));
            return;
        }
        // 如果当前这个位置的值已经出现过了，那么不需要继续向下走了，因为后面的可能已经被统计过
        // 例如有两种路径到达第十行都是一样的值，那么就不需要从这个一样的值继续往下走
        if (memo[startIndex][cnt]) return;

        memo[startIndex][cnt] = true;
        for (int i = 0; i < n; i++) {
            cnt += mat[startIndex][i];
            if (cnt - target > 0 && cnt - target > min) break;
            backtrackingMinimize(mat, target, startIndex + 1, cnt);
            cnt -= mat[startIndex][i];
        }
    }
}
